﻿namespace Gobang.ToolClass.PVE
{
    /*
     * 人机博弈
     * 改进前的 AI 眼光短浅，只顾当前局面。改进后的 AI 使用 DFS（深度优先搜索）进行对博弈树的遍历，再挑选分值最大的根节点进行落子。具体的，就是先算出每个点的当前分值，再递归去寻找落子后对方分值，把这两个值相减，就可以得到这个位置真正的分值。

        可是如果直接递归，时间复杂度很大，大约是 O((192)n)（ n 为递归次数），于是就加入了两个剪枝（只查找周边有棋子的空位）（如果位置初始分值大于最大分值才递归）和层数限制（只考虑以后4步）。
     */
    public class ManMachine
    {
        // - | \ / 四个方向
        private readonly int[] dx = { 1, 0, 1, 1 };
        private readonly int[] dy = { 0, 1, 1, -1 };
        // 最优解数
        private int _ons = 0;
        //评分表
        private int[,] Score =
            {
                { 0, 80, 250, 500, 500 }, // 防守0子
	            { 0, 0,  80,  250, 500 }, // 防守1子
	            { 0, 0,  0,   80,  500 }  // 防守2子
            };
        // 棋盘
        private readonly int[,] BOX;
        private readonly int _boxSize;
        // 层数，越高越耗时
        private const int STOREY = 3;
        // 最优y坐标
        private readonly int[] MAXxs;
        // 最优x坐标
        private readonly int[] MAXys;
        private readonly Random _random;
        public ManMachine(int[,] box)
        {
            BOX = box;
            _boxSize = box.GetLength(0);
            MAXxs = new int[_boxSize * _boxSize];
            MAXys = new int[MAXxs.Length];
            _random = new Random();
        }
        public Seat BestSeat(int color, int storey)
        {
            if (storey == 0)
                _ons = 0;

            int maxNumber = (int)(-(1e+9));    //最佳分数
            for (int i = 0; i < _boxSize; i++)
            {
                for (int j = 0; j < _boxSize; j++)
                {
                    // 是否为空位
                    if (BOX[i, j] != 0)
                        continue;
                    //遍历每一个空位置
                    int length;        //当前方向长度
                    int emeny;         //当前方向敌子
                    int nowi = 0;      //现在遍历到的y坐标
                    int nowj = 0;      //现在遍历到的x坐标
                    int thescore = 0;  //这个位置的初始分数
                    int isHas = 0;//判断周边有没有棋子
                    for (int k = 0; k < 4; k++)
                    {
                        nowi = i;
                        nowj = j;
                        nowi += dx[k];
                        nowj += dy[k];
                        if (nowi >= 0 && nowj >= 0
                            && nowi < _boxSize && nowj < _boxSize
                            && BOX[nowi, nowj] != 0)
                        {
                            isHas = 1;
                            break;
                        }
                        nowi = i;
                        nowj = j;
                        nowi += dx[k];
                        nowj += dy[k];
                        if (nowi >= 0 && nowj >= 0
                            && nowi < _boxSize && nowj < _boxSize
                            && BOX[nowi, nowj] != 0)
                        {

                            isHas = 1;
                            break;
                        }
                        nowi = i;
                        nowj = j;
                        nowi -= dx[k];
                        nowj -= dy[k];
                        if (nowi >= 0 && nowj >= 0
                            && nowi < _boxSize && nowj < _boxSize
                            && BOX[nowi, nowj] != 0)
                        {

                            isHas = 1;
                            break;
                        }
                        nowi = i;
                        nowj = j;
                        nowi -= dx[k];
                        nowj -= dy[k];
                        if (nowi >= 0 && nowj >= 0
                            && nowi < _boxSize && nowj < _boxSize
                            && BOX[nowi, nowj] != 0)
                        {

                            isHas = 1;
                            break;
                        }
                    }
                    // 如果周围没有棋子，就不用递归了
                    if (isHas == 0)
                        continue;
                    //自己
                    BOX[i, j] = color;//尝试下在这里
                    for (int k = 0; k < 4; k++)
                    {
                        //检测四个方向
                        length = 0;
                        emeny = 0;
                        nowi = i;
                        nowj = j;
                        while (nowi < _boxSize && nowj < _boxSize && nowi >= 0 && nowj >= 0 && BOX[nowi, nowj] == color)
                        {
                            length++;
                            nowj += dy[k];
                            nowi += dx[k];
                        }
                        if (nowi < 0 || nowj < 0 || nowi >= _boxSize || nowj >= _boxSize || BOX[nowi, nowj] == -color)
                        {
                            emeny++;
                        }
                        nowi = i;
                        nowj = j;
                        while (nowi < _boxSize && nowj < _boxSize && nowi >= 0 && nowj >= 0 && BOX[nowi, nowj] == color)
                        {
                            length++;
                            nowj -= dy[k];
                            nowi -= dx[k];
                        }
                        if (nowi < 0 || nowj < 0 || nowi >= _boxSize || nowj >= _boxSize || BOX[nowi, nowj] == -color)
                        {
                            emeny++;
                        }
                        length -= 2;//判断长度
                        if (length > 4)
                        {
                            length = 4;
                        }
                        if (Score[emeny, length] == 500)
                        {
                            //己方胜利，结束递归
                            BOX[i, j] = 0;
                            return new Seat(i, j, Score[emeny, length]);
                        }
                        thescore += Score[emeny, length];
                        length = 0;
                        emeny = 0;
                    }
                    //敌人（原理同上）
                    BOX[i, j] = -color;
                    for (int k = 0; k < 4; k++)
                    {
                        length = 0;
                        emeny = 0;
                        nowi = i;
                        nowj = j;
                        while (nowi < _boxSize && nowj < _boxSize && nowi >= 0 && nowj >= 0 && BOX[nowi, nowj] == -color)
                        {
                            length++;
                            nowj += dy[k];
                            nowi += dx[k];
                        }
                        if (nowi < 0 || nowj < 0 || nowi >= _boxSize || nowj >= _boxSize || BOX[nowi, nowj] == color)
                        {
                            emeny++;
                        }
                        nowi = i;
                        nowj = j;
                        while (nowi < _boxSize && nowj < _boxSize && nowi >= 0 && nowj >= 0 && BOX[nowi, nowj] == -color)
                        {
                            length++;
                            nowj -= dy[k];
                            nowi -= dx[k];
                        }
                        if (nowi < 0 || nowj < 0 || nowi >= _boxSize || nowj >= _boxSize || BOX[nowi, nowj] == color)
                        {
                            emeny++;
                        }
                        length -= 2;
                        if (length > 4)
                        {
                            length = 4;
                        }
                        if (Score[emeny, length] == 500)
                        {
                            BOX[i, j] = 0;
                            return new Seat(i, j, Score[emeny, length]);
                        }
                        thescore += Score[emeny, length];
                        length = 0;
                        emeny = 0;
                    }
                    BOX[i, j] = 0;
                    //如果已经比最高分数小，就没必要递归了
                    if (thescore >= maxNumber)
                    {
                        if (storey < STOREY)
                        {
                            //只能找4层，否则时间太长
                            BOX[i, j] = color;
                            //递归寻找对方分数
                            int nowScore = thescore - BestSeat(-color, storey + 1).Score;//递归求出这个位置的分值
                            BOX[i, j] = 0;
                            if (nowScore > maxNumber)
                            {
                                //比最高分值大
                                maxNumber = nowScore;
                                if (storey == 0)
                                {
                                    //第一层
                                    _ons = 0;//清空数组
                                }
                            }
                            if (storey == 0)
                            {
                                //第一层
                                if (nowScore >= maxNumber)
                                {
                                    //把当前位置加入数组
                                    MAXxs[_ons] = i;
                                    MAXys[_ons] = j;
                                    _ons++;
                                }
                            }
                        }
                        else
                        {
                            //如果递归到了最后一层
                            if (thescore > maxNumber)
                            {
                                //直接更新
                                maxNumber = thescore;
                            }
                        }
                    }
                }
            }
            if (storey == 0)
            {
                //第一层
                //随机化落子位置
                _ons = _ons == 0 ? 1 : _ons;
                int mynum = _random.Next(0, _boxSize) % _ons;
                return new Seat(MAXxs[mynum], MAXys[mynum], maxNumber);
            }
            // 其它层
            return new Seat(0, 0, maxNumber);
        }
    }
}
